/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package ga_checkpoint5;

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

/**
 *
 * @author Asif Dipon, Harshal Joshi
 */
public class Main {

    //constant static variables that define the max number of generations the
    //algorithm should run for and the range in which the entity's chromosomes
    //may fall under
    final static int MAX_NUM_GENERATION = 100;
    final static int MAX_POP_SIZE = 10;
    final static int RANGE_MAX = 500;
    final static double MAX_PARENT_SURVIVAL_RATE = 4.0;
    final static double CROSSOVER_RATE = 0.75;  //Currently unused
    final static double MUTATION_RATE = 0.001;  //Currently unused

    static List<City> cityList = new ArrayList();

    /**The main method. It processes command line arguments and starts the
     * primary program.
     * @param args the command line arguments
     */
    public static void main(String[] args) {

        //Generate a list of random cities        
        cityList = getRandomCities(10);
        printCityList(cityList);

        //The initial population
        List<TourPath> genZero = createGenZero(cityList);

        //Print the info for the 0th generation.
        printInfo(genZero, 0);

        //Running tests for different parameters. All other parameters stay costant
        System.out.println("\nTest 1: 100% Elitism");
        doTask(genZero, 4, 0, 0, "dataElite100.txt");

        System.out.println("\nTest 2: 75% Elitism");
        doTask(genZero, 3, 0, 0, "dataElite75.txt");

        System.out.println("\nTest 3: 50% Elitism");
        doTask(genZero, 2, 0, 0, "dataElite50.txt");

        System.out.println("\nTest 4: 25% Elitism");
        doTask(genZero, 1, 0, 0, "dataElite25.txt");

        System.out.println("\nTest 5: 0% Elitism");
        doTask(genZero, 0, 0, 0, "dataElite0.txt");

        System.out.println("\nTest 6: Parent Selection Random");
        doTask(genZero, 4, 0, 0, "dataParSelRandom.txt");

        System.out.println("\nTest 7: Parent Selection Random Best");
        doTask( genZero, 4, 1, 0, "dataParSelRandomBest.txt");

        System.out.println("\nTest 8: Population Selection Best Fitness");
        doTask( genZero, 4, 0, 0, "dataPopSelBestFit.txt");

        System.out.println("\nTest 9: Population Selection Random Best");
        doTask( genZero, 4, 0, 1, "dataPopSelRandomBest.txt");

        System.out.println("\n\nProgram Complete.");
    }

    /**
     * This runs the algorithm. It creates the 0th generation. Then it spawns 10
     * new generations through crossover and mutation. At each generation, the 10
     * fittest entities survive to live into the next generation.
     * @param par_surv  The parents survival rate
     * @param par_sel   How parents are selected for mutation and crossover
     * @param pop_sel   How individuals are selected from the population for the next generation
     * @param outFileName
     */
    public static void doTask(List<TourPath> genZero, int par_surv,
            int par_sel, int pop_sel, String outFileName){
        
        //This is a list of the best fitness tour path per generation
        List<TourPath> bestPerGen = new ArrayList<TourPath>();
        //This is a list of the worst fitness tour path per generation
        List<TourPath> worstPerGen = new ArrayList<TourPath>();
        List<Double> avgFitnessPerGen = new ArrayList<Double>();
        //Create the 0th generation with random values.
        List<TourPath> population = genZero;
        int genNum = 0;        
        //Create new generations until the limit is reached.
        while(genNum < MAX_NUM_GENERATION){
            //Create a list of child entities that will be created through crossover and mutation
            List<TourPath> survivalPool = new ArrayList<TourPath>();
            //Do crossover and mutation 5 times each
            for( int i = 0; i<10; i++){

                //Select random parents from population
                if (par_sel == 0){
                //create spawn through crossover
                TourPath p1 = selectRandomFromPopulation(population);
                TourPath p2 = selectRandomFromPopulation(population);
                TourPath child1 = doCrossover(p1, p2);
                doGeneticRepair(child1);
                survivalPool.add(child1);
                //create spawn through mutation
                TourPath p3 = selectRandomFromPopulation(population);
                TourPath child2 = doMutation(p3);
                doGeneticRepair(child2);
                survivalPool.add(child2);
                }

                //Select random parents from a subset of the population with highest fitness
                else if (par_sel==1){
                    //create spawn through crossover
                    TourPath p1 = selectRandomBestFromPopulation(population);
                    TourPath p2 = selectRandomBestFromPopulation(population);
                    TourPath child1 = doCrossover(p1, p2);
                    doGeneticRepair(child1);
                    survivalPool.add(child1);
                    //create spawn through mutation
                    TourPath p3 = selectRandomBestFromPopulation(population);
                    TourPath child2 = doMutation(p3);
                    doGeneticRepair(child2);
                    survivalPool.add(child2);
                }
            }
            
            //Based on the number of parents that can survive each generation, the
            //appropriate number of them are added to the survival pool, those with higher
            //fitness get priority.
            if(par_surv > 0){
                Collections.sort(population);
                int totalSurvivors = (int)(par_surv/MAX_PARENT_SURVIVAL_RATE * population.size());
                List<TourPath> t = population.subList(0, totalSurvivors);
                for (TourPath a: t){
                    if (!survivalPool.contains(a)){
                        a.numTimesSelected++;
                        survivalPool.add(a);
                    }
                }
            }

            //Remove the population
            population.clear();
            //add all spawn and survivng parents to the survival pool
            population.addAll(survivalPool);

            //Fitness based selection. Choose top10 best.
            if (pop_sel ==0){

                //Sort the population based on fitness, in ascending order.
                Collections.sort(population);
                int size = population.size();
                //Population Selection
                List<TourPath> top10 = new ArrayList<TourPath>();
                for(int i=0; top10.size()<MAX_POP_SIZE && i<size; i++){
                    TourPath temp = population.get(i);
                    if(!top10.contains(temp)){
                        top10.add(temp);
                    }
                }
                population = top10;
            }

            //Randomly selects 10 individuals from teh population who are in the
            //top 75% in terms if fitness
            if (pop_sel==1){

                //Population Selection
                List<TourPath> survivors = new ArrayList<TourPath>();
                for(int i=0; survivors.size()<MAX_POP_SIZE && i<population.size(); i++){
                    TourPath temp = selectRandomBestFromPopulation(population);
                    if(!survivors.contains(temp)){
                        survivors.add(temp);
                    }
                }
                population = survivors;
            }           

            //Sort the population and collect statistical data
            Collections.sort(population);
            bestPerGen.add(population.get(0));
            worstPerGen.add(population.get(population.size()-1));
            avgFitnessPerGen.add(getAvgFitnessForTour(population));
            
            genNum++;
            //Print the info for the generation
            //Ommitted because it is not need for this submission.
            //printInfo(population, genNum);

        }

        //Write the stats that have been collected to the file.
        writeStatsToFile(outFileName, bestPerGen, worstPerGen, avgFitnessPerGen);

        //At the end of the run, print the info for the best path.
        TourPath best = population.get(0);
        System.out.println("\nBest path\nId=" + best.id + "\nTour Path=" + best + "\nFitness: " + best.getFitness());
    }

    /**
     * This method creates generation 0 through random assignment of chromosomes.
     * @return A list containing 10 randomly generated entities.
     */
    public static List<TourPath> createGenZero(List<City> cityList){
        List<TourPath> population = new ArrayList<TourPath>();

        Random rand = new Random();
        //Create random tour paths of the cities to fill up the population
        for(int i =0; i<MAX_POP_SIZE; i++){
            int uid = UIDGen.getInstance().getNextUID();
            TourPath e = new TourPath(uid);
            for(int j=0; j<cityList.size(); j++){
                if(e.tour.size() > 0){
                    //Add the current city to a random location in the list.
                    e.tour.add(rand.nextInt(e.tour.size()+1), cityList.get(j));
                } else{
                    e.tour.add(cityList.get(j));
                }
            }
            population.add(e);
        }

        return population;
    }

    /**
     * Creates cities with random coordinates.
     * @param size  The total number of cities to create.
     * @return  A list containing all the cities.
     */
    private static List<City> getRandomCities(int size) {
        Random rand = new Random();
        cityList = new ArrayList<City>();
        for(int i= 0; i<size; i++){
            int x = rand.nextInt(RANGE_MAX + 1);
            int y = rand.nextInt(RANGE_MAX + 1);
            char id = (char)('A' + i);
            City c = new City(id, x, y);
            cityList.add(c);
        }
        return cityList;
    }

    /**
     * This method takes two parent entities and creates a child entity
     * through crossover of genes.
     * @param parent1   The first parent to take genes from.
     * @param parent2   The second parent to take genes from
     * @return  A new child entity
     */
    public static TourPath doCrossover(TourPath parent1, TourPath parent2){
    	TourPath child = new TourPath(UIDGen.getInstance().getNextUID());
    	Random rand = new Random();
        //Select a random point in the first parent to split at.
        int splitter = rand.nextInt(parent1.tour.size());

        for(int j=0; j<splitter; j++){
            if(!child.tour.contains(parent1.tour.get(j))){
                City d = parent1.tour.get(j);
                child.tour.add(d);
            }
        }

        //fill up the remaining slots in the child with unique cities from parent2's
        //path at random indices.
        for(City c:parent2.tour){
            if(!child.tour.contains(c)){
                //child.tour.add(c);
                int cSize = child.tour.size();
                if (cSize > 0){
                    int randIndex = rand.nextInt(child.tour.size());
                    child.tour.add(randIndex, c);
                }else{
                    child.tour.add(c);
                }
            }
        }
    	return child;
    }

    /**
     * This method creates a child entity through the mutation of one or more
     * genes of a parent entity.
     * @param parent    The entity whose genes will mutate
     * @return  A child entity that is different from its sole parent
     */
    public static TourPath doMutation(TourPath parent){
    	//choose two random indexes that are unique
    	Random rand = new Random();
        int mutateChoice = rand.nextInt(2);
        //Get two unique random numbers
       	int randNum = 0;
        int randNum2 = 0;
        while (randNum >= randNum2){
            randNum = rand.nextInt(parent.tour.size());
            randNum2 = rand.nextInt(parent.tour.size());
        }
        //Create a child tour path based on the parent provided.
       	TourPath child = new TourPath(UIDGen.getInstance().getNextUID());
        child.tour.addAll(parent.tour);
        if(mutateChoice==0){
            //Swap the child's cities at the selected indexes.
            City c = parent.tour.get(randNum2);
            child.tour.set(randNum2, parent.tour.get(randNum));
            child.tour.set(randNum, c);
        }else{

            List<City> mutated = child.tour.subList(randNum, randNum2);
            Collections.reverse(mutated);

            for(int j=0; j<mutated.size(); j++){
                child.tour.set(randNum+j, mutated.get(j));
            }
            
            //Swap all the cities between the two random indexes
            /*for(int i=0; (randNum+i)<(randNum2-i); i++){
                City temp = child.tour.get(randNum+i);
                City temp2 = child.tour.get(randNum2-i);
                child.tour.set(randNum+i, temp2);
                child.tour.set(randNum2-1, temp);
            }*/
            doGeneticRepair(child);
        }
        
        //Return the newly created child city.
        return child;
    }

    /**
     * Prints the list of cities given
     * @param cityList  The list of cities.
     */
    public static void printCityList(List<City> cityList){
        System.out.println("\nCity List");
        System.out.println("CityID\tXCor\tYCor");
        for(City c: cityList){
            System.out.println("" + c.id + "\t\t" + c.xcor + "\t\t" + c.ycor);
        }
    }

    /**
     * This method prints the relevant information for each generation: generation
     * number, the min/max fitness, and the population's information.
     * @param population    The list containing the population.
     * @param genNum    The generation number
     */
    public static void printInfo(List<TourPath> population, int genNum){
        //Print the generation number
        System.out.println("\n\nGeneration #" + genNum);
        //Sort the population
        Collections.sort(population);
        //Print out the min and max fitness among the population
        System.out.println("\nMin fitness: " + population.get(0).getFitness());
        System.out.println("Max fitness: " + population.get(population.size()-1).getFitness());
        //Print out each individual in the population and their information.
        System.out.println("\nID \t\t Fitness \t\t\t Path");
        for(TourPath e : population){
            System.out.print("\n" + e.id + " \t " + e.getFitness() + " \t " + e);
        }
        System.out.println();

    }

    /**
     * Returns a pseudorandom member from a population
     * @param pop
     * @return
     */
    public static TourPath selectRandomFromPopulation(List<TourPath> pop){
        Random rand = new Random();
        int index = rand.nextInt(pop.size());
        return pop.get(index);
    }

    /**
     * Selects a random TourPath from the population from the a subset of the total
     * population, the ones that have the highest fitness.
     * @param pop
     * @return
     */
    public static TourPath selectRandomBestFromPopulation(List<TourPath> pop){
        Collections.sort(pop);
        Random rand = new Random();
        TourPath retVal = pop.get(rand.nextInt((int)(pop.size()* CROSSOVER_RATE)));
        return retVal;
    }

    /**
     * Returns a random double between the ranges specified.
     * @param rangeMin  The lower bound
     * @param rangeMax  The upper bound
     * @return  A pseudorandom double within the specified range.
     */
    public static double getRandomDouble(double rangeMin, double rangeMax){
        double retVal = 0;
        Random rand = new Random();
        retVal = ((rangeMax-rangeMin) * rand.nextDouble()) + rangeMin;
        return retVal;
    }

    /**
     * Writes information to file about the best, the worst, and average fitness of every generation.
     * @param file_name
     * @param bestPerGen
     * @param worstPerGen
     * @param avgFitnessPerGen
     */
    private static void writeStatsToFile(String file_name, List<TourPath> bestPerGen, List<TourPath> worstPerGen, List<Double> avgFitnessPerGen) {
        try{
            FileWriter fstream = new FileWriter(file_name);
            BufferedWriter out = new BufferedWriter(fstream);
            String header = "\nGenID \t BestFitness \t BestID \t BestPath \t WorstFitness \t WorstID \t WorstPath \t AverageFitness";
            out.write(header);
            out.flush();
            for(int i=0; i<bestPerGen.size(); i++){
                TourPath curBest = bestPerGen.get(i);
                TourPath curWorst = worstPerGen.get(i);
                double avgFitness = avgFitnessPerGen.get(i).doubleValue();
                String data = "\n" + (i+1) + "\t" +curBest.getFitness() + "\t" + curBest.id + "\t" + curBest.tour.toString() + "\t";
                data += curWorst.getFitness() + "\t" + curWorst.id + "\t" + curWorst.tour.toString() + "\t" + avgFitness;
                out.write(data);
                out.flush();
            }
            out.close();
        }
        catch (Exception e){
            e.printStackTrace();
        }
    }

    /**
     * Computes the average fitness for all the TourPaths in a population
     * @param pop   The population to analyze.
     * @return A double containing
     */
    public static Double getAvgFitnessForTour(List<TourPath> pop){
        double sum = 0;
        int count = 0;
        for(TourPath t: pop){
            sum += t.getFitness();
            count++;
        }
        return new Double(sum/count);
    }

    /**
     * Does genetic repair by removing duplicates and adding missing cities
     * @param child     
     */
    private static void doGeneticRepair(TourPath child) {
        List<City> seen = new ArrayList<City>();
        List<City> toBeRemoved = new ArrayList<City>();

        //Search for duplicates in the child's path and flag them
        for(City c: child.tour ){
            if (!seen.contains(c)){
                seen.add(c);
            }
            else{
                toBeRemoved.add(c);
            }
        }

        //Remove all duplicates
        for(City c: toBeRemoved ){
            int index = child.tour.lastIndexOf(c);
            child.tour.remove(index);
        }

        //Add any cities that are missing.
        for(City c: cityList ){
            if (!child.tour.contains(c)){
                child.tour.add(c);
            }
        }

    }

}
